package Sort;

import org.junit.Test;

/**
 * @author yyq
 * @create 2021-10-15 21:29
 * 希尔排序
 * 分段直接插入排序
 * 如果是奇数 0 - 1 2 3 4
 */
public class ShellSort {
    public static void shellSort(int[] arr){
        int l=arr.length;
        int gap=l;        //步长 也是第一层循环的开始
        int members;      //组中元素个数

        while (true){
            gap=gap/2;
            members=l/gap;
            //对每段进行直接插入排序
            //假设 l=10 第一次 gap=5 members=2 最后一次 gap=1 members=10
            for (int i = 0; i < gap; i++) {
                //pre有序  loc之后无序
                int loc=i+gap;
                int pre=i;
                for (int j=0; j<members; j++){
                    if(loc>=l) break;
                    if(arr[loc]<arr[pre]){ //当前方的大于后方的 交换 否则无变化
                        int temp;
                        temp=arr[loc];
                        arr[loc]=arr[pre];
                        arr[pre]=temp;
                    }
                    pre=loc;
                    loc=loc+gap;
                }
            }
            //结束条件 步长为一执行完成之后
            if(gap==1) break;
        }

    }
    @Test
    public void test(){
        int[] a={213,2,3,2,4,5,6,7,8,21,3};
        shellSort(a);
        for (int i : a) {
            System.out.println(i);
        }
    }
}
